package com.smday.recursion;

/**
 * @author Summerday
 */
public class Maze {

    public static void main(String[] args) {

        //创建二维数组,模拟迷宫

        int[][] map = new int[8][7];

        //上下置1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //左右置1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        //设置挡板

        map[3][1] = 1;
        map[3][2] = 1;

        //输出地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }


        //使用递归回溯,给小球招路,map为引用类型,无论进行多少次递归,都是改变的同一个区域
        setWay(map,1,1);
        System.out.println("====================");
        //输出地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }


    }

    /**
     * 1. map:地图
     * 2. i,j:表示出发的位置
     * 3. 如果找到map[6][5]表示找到通路
     * 4. map[i][j] 为0表示该店还没有走,为1表示墙,2表示通路,3表示该位置已经走过,但不通
     * 5. 确定策略:下->右->上->左
     *
     *
     */

    /**
     * 递归回溯
     * @param map 地图
     * @param i 从i行开始
     * @param j 从j列开始
     * @return 找到通路,返回true,否则false
     */
    public static boolean setWay(int[][] map,int i,int j){
        //通路已经找到
        if(map[6][5] == 2){
            return true;

        }else {
            //如果当前这个点还没有走
            if(map[i][j] == 0){
                //假定可以走通
                map[i][j] = 2;

                if(setWay(map,i+1,j)){
                    return true;
                }else if(setWay(map,i,j+1)){
                    return true;
                }else if(setWay(map,i-1,j)){
                    return true;
                }else if(setWay(map,i,j-1)){
                    return true;
                }else {
                    //该点走不通
                    map[i][j] = 3;
                    return false;
                }

            }else {
                //map[i][j]!=0,可能为1,3
                return false;
            }
        }

    }

}
